public class Leetcode {
}

//leetcode:115:不同的子序列
class Solution1 {
    public int numDistinct(String s, String t) {
        int n = s.length(), m = t.length();

        //创建一个dp表，表示s字符串中0~j区间的所有子序列中有多少个t字符串中0~i的子串
        int[][] dp = new int[m+1][n+1];
        //如果t字符串为空串，而0到每个j位置都有一个子序列为空串，所以t字符串为空串0~j每个位置的个数都为1
        for(int j = 0; j <= n; j++) dp[0][j] = 1;

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果s子序列的最后一个位置不包含j位置元素，就要到前j-1个元素位置去找t字符串中0到i的子串
                dp[i][j] = dp[i][j-1];
                //包含j位置元素，就要到前j-1位置找0~i-1的子串
                if(t.charAt(i-1) == s.charAt(j-1)){
                    //将这两种情况加在一起就是我们0~j位置中0~i位置子串的个数
                    dp[i][j] += dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}

//leetcode:44:通配符匹配
class Solution2 {
    public boolean isMatch(String ss, String pp) {
        int m = ss.length() , n = pp.length();
        ss = " " + ss;pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //创建一个dp表，表示p中0~j位置的所有子串，是否能够完全匹配s中0~i位置的所有子串
        boolean[][] dp = new boolean[m+1][n+1];
        //如果都为空串，就代表都能匹配
        dp[0][0] = true;
        //如果j位置为*，同时s子串为空串，依然能够进行匹配，因为*可以匹配任意序列，但是j位置不为*了，那么后面的所有位置就都不能进行匹配了
        for(int j = 1; j <= n; j++){
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果j位置为*，就要进行判断*要匹配几个字符，如果都将这个*匹配的字符在s中去掉，此时就要判断p字符串中0~j-1位置大的所有子串是否能与s字符串中0~i-(*匹配的字符个数)匹配
                if(p[j] == '*'){
                    //如果有一个成立就代表，可以全部进行匹配
                    dp[i][j] = dp[i][j-1] || dp[i-1][j];
                }else {
                    //如果不为*，并且i位置的元素和p位置的元素相同或者p位置的元素为'?'('?'k可以匹配任意一个字符),就要判断0~j-1位置的所有子串是否能够完全匹配0~i-1位置的所有子串
                    dp[i][j] = (s[i] == p[j] || p[j] == '?') && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}